home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
MacHack 1999
/
MacHack 1999.toast
/
The Hacks
/
ReaderMouse
/
LetterFind.c
next >
Wrap
Text File
|
1999-06-22
|
20KB
|
630 lines
/* algorithm:
Find a letter in the immediate vicinity of the mouse.
(the middle of the gworld data we are given. (what about edges?))
For each font and each point size
on a rectangle pointsize*2+1 tall and maxLetterWidth*2+1 wide
correlate all the letters,
store max correlation for each letter. (Why not just max over font and point size?)
Store max correlation for font and point size allong with the letter with
max correlation and it's location.
(What about location? Closeness to the pointer should also be important.)
Find the word that letter belongs to.
Assume that which ever font and point size has the highest correlation is the
font and point size for that word.
Using the location of the found letter perform a horizontal sweep of correlations
to determine the rest of the letters in the word.
Speak the word.
Store the rectangle for the word and do no processing until the mouse leaves that
rectangle. (Later. Now we are processing movies.)
*/
#include <math.h>
#include <quickdraw.h>
#include "LetterFind.h"
#include "WorkFunctions.h"
/* globals */
short gPointSizes[NUM_POINT_SIZES] = {9, 10, 12, 14};
short gFonts[NUM_FONTS] = {0,0,0};
Str255 gFontNames[NUM_FONTS] = {"\pGeneva","\pMonaco","\pSystem"};//,"\pSystem"
char gLetters[NUM_LETTERS+1] =
" abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";//',.""<>`1234567890[]~!@#$%^&*(){}/=?+-_\|;:";
// ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
// 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95
FontData gFontDatas[NUM_FONTS * NUM_POINT_SIZES];
short gBytesPerPixel = 1;
const short LETTER_PAD = LETTER_RIGHT_PAD + LETTER_LEFT_PAD;
const short LETTER_KERNEL_DIFF = LETTER_PAD - LETTER_DIFF_MINUS;
const short gScreenHGrabSize = 120;
const short gScreenVGrabSize = 50;
GWorldPtr gScreenHDiff, gScreenVDiff;
void InitFontNumbers(void)
{
short font;
for (font=0; font<NUM_FONTS; font++)
{
GetFNum(gFontNames[font],&(gFonts[font]));
}
}
/* initialize the fonts */
OSErr InitializeFonts()
{
FontData *theFontData;
short font, pointSize;
short letter, kernelWidth, kernelOffset, baseLine;
int gWorldWidth=0, pixelDepth;
GrafPtr savePort;
GDHandle saveGD;
Rect boundsRect = {0,0,0,0};
OSErr err;
FontInfo theFontInfo;
// debugging info
Ptr baseAddr;
// Save the drawing environment.
GetPort(&savePort);
saveGD = GetGDevice();
for (font=0; font < NUM_FONTS; font++)
for (pointSize=0; pointSize < NUM_POINT_SIZES; pointSize++)
gFontDatas[font * NUM_POINT_SIZES + pointSize].kernelBitmap = 0;
InitFontNumbers();
for(font=0; font < NUM_FONTS; font++)
{
for (pointSize = 0; pointSize < NUM_POINT_SIZES; pointSize++)
{
theFontData = &FONT_DATA(font,pointSize);
// change font in original gworld, just so we keep the font in each gWorld
// the same as it's font data. Not necessary, but it might help avoid accidental
// problems latter.
SetPort(savePort);
// set font
TextFont(gFonts[font]);
// set point size
TextSize(gPointSizes[pointSize]);
// set style to plain
TextFace(0);
// set mode to over write
TextMode(srcCopy);
/* allocate gWorld */
gWorldWidth = 0;
for(letter=0;letter<NUM_LETTERS;letter++) gWorldWidth += CharWidth(gLetters[letter])+LETTER_PAD;
boundsRect.right = gWorldWidth;
GetFontInfo(&theFontInfo);
theFontData->maxHeight = theFontInfo.ascent+theFontInfo.descent;
// adding one space between letters. (+2) then each letter is one thiner since
// we're diffing, so edges are not meaningful. (-1) = (+1)
theFontData->maxWidth = theFontInfo.widMax + LETTER_PAD - LETTER_DIFF_MINUS;
baseLine = theFontInfo.ascent;
boundsRect.bottom = theFontData->maxHeight;
//pixelDepth = ((CGrafPort*)savePort)->portPixMap[0]->pixelSize;
pixelDepth = gBytesPerPixel * 8;
err = NewGWorld(&(theFontData->kernelBitmap), pixelDepth, &boundsRect, nil, nil, 0);
if (err != noErr || theFontData->kernelBitmap == nil) goto initializeFontsDeath;
SetPort((GrafPort*)(theFontData->kernelBitmap));
baseAddr = GetPixBaseAddr(GetGWorldPixMap(theFontData->kernelBitmap));
// White out gWorld so we can add spaces between the letters if we want.
//PenMode(patCopy);
//ForeColor(whiteColor);
EraseRect(&boundsRect);
//ForeColor(blackColor);
baseAddr = GetPixBaseAddr(GetGWorldPixMap(theFontData->kernelBitmap));
//set font
TextFont(gFonts[font]);
TextSize(gPointSizes[pointSize]);
TextFace(0);
TextMode(srcCopy);
theFontData->kernelOffset[0] = 0;
kernelOffset = 0;
for(letter = 0; letter < NUM_LETTERS; letter++)
{
// draw letter over one pixel to put a space on each side.
MoveTo(kernelOffset+LETTER_LEFT_PAD, baseLine);
DrawChar(gLetters[letter]);
kernelWidth = CharWidth(gLetters[letter]);
kernelWidth+=LETTER_PAD; // add extra space on each side of letters.
kernelWidth-=LETTER_DIFF_MINUS; // remove boundary since we're doing diffing.
theFontData->kernelWidth[letter] = kernelWidth;
kernelOffset += kernelWidth + LETTER_DIFF_MINUS;
if(letter!=(NUM_LETTERS-1))
theFontData->kernelOffset[letter+1] = kernelOffset;
}
ConvertToHDiffKernel(theFontData->kernelBitmap);
}
}
// Initialize Difference GWorlds.
err = InitializeDifferenceGWorlds();
if (err != noErr) goto initializeFontsDeath;
// Restore the drawing environment.
SetPort(savePort);
SetGDevice(saveGD);
return 0;
initializeFontsDeath:
SetPort(savePort);
SetGDevice(saveGD);
for (font=0; font < NUM_FONTS; font++)
for (pointSize=0; pointSize < NUM_POINT_SIZES; pointSize++)
if(FONT_DATA(font,pointSize).kernelBitmap != nil)
DisposeGWorld(FONT_DATA(font,pointSize).kernelBitmap);
return -1;
}
OSErr InitializeDifferenceGWorlds(void)
{
OSErr err;
Rect boundsRect = {0,0,gScreenVGrabSize,gScreenHGrabSize};
short pixelDepth = 8;
err = NewGWorld(&gScreenVDiff, pixelDepth, &boundsRect, nil, nil, 0);
if (err != noErr || gScreenVDiff == nil) goto initializeDifferenceGWorldsDeath;
err = NewGWorld(&gScreenHDiff, pixelDepth, &boundsRect, nil, nil, 0);
if (err != noErr || gScreenHDiff == nil) goto initializeDifferenceGWorldsDeath;
return noErr;
initializeDifferenceGWorldsDeath:
if (gScreenHDiff != nil) DisposeGWorld(gScreenHDiff);
if (gScreenVDiff != nil) DisposeGWorld(gScreenVDiff);
return -1;
}
/* currently only handles 8 and 16 bits. */
void ConvertToHDiffKernel(GWorldPtr inGWorld)
{
PixMapHandle pixMap;
short rowBytes;
Ptr baseAddr;
short x,y;
short bitsPerPixel;
short height;
pixMap = GetGWorldPixMap(inGWorld);
LockPixels(pixMap);
rowBytes = ROWBYTES(pixMap[0]->rowBytes);
height = pixMap[0]->bounds.bottom - pixMap[0]->bounds.top;
baseAddr = pixMap[0]->baseAddr;
bitsPerPixel = pixMap[0]->pixelSize;
switch(bitsPerPixel)
{
case 8:
for (y=0; y <height; y++)
for (x=0; x<rowBytes-1; x++)
if (*(baseAddr + y*rowBytes + x) != *(baseAddr + y*rowBytes + x +1))
*(baseAddr + y*rowBytes + x) = 1;
else
*(baseAddr + y*rowBytes + x) = -1;
break;
case 16:
for (y=0; y <height; y++)
for (x=0; x<rowBytes-2; x+=2)
if ((*(baseAddr + y*rowBytes + x) & MASK_16) != (*(baseAddr + y*rowBytes + x+2) & MASK_16))
*(short*)(baseAddr + y*rowBytes + x) = 1;
else
*(short*)(baseAddr + y*rowBytes + x) = -1;
break;
}
UnlockPixels(pixMap);
}
/* currently only handles 16 bit color. */
void HorizontalDifference(GWorldPtr screenGWorld)
{
PixMapHandle screenPixMapH, diffPixMapH;
short screenRowBytes, diffRowBytes, bitDepth;
short x,y,diffY;
Ptr diffBits;
short *screenBits; // 16 bit value
Rect screenBounds, diffBounds;
long diffSum;
char diffMax=0, diffMin=255;
screenPixMapH = GetGWorldPixMap(screenGWorld);
LockPixels(screenPixMapH);
bitDepth = screenPixMapH[0]->pixelSize;
screenRowBytes = ROWBYTES(screenPixMapH[0]->rowBytes);
diffPixMapH = GetGWorldPixMap(gScreenHDiff);
LockPixels(diffPixMapH);
diffRowBytes = ROWBYTES(diffPixMapH[0]->rowBytes);
RECT_EQUAL(screenBounds, screenPixMapH[0]->bounds);
RECT_EQUAL(diffBounds, gScreenHDiff->portRect)
CommonRect(&diffBounds, &screenBounds);
for(y = screenBounds.top,diffY = diffBounds.top; y < screenBounds.bottom; y++,diffY++)
{
screenBits = (short*)(screenPixMapH[0]->baseAddr + y*screenRowBytes) + screenBounds.left;
diffBits = diffPixMapH[0]->baseAddr + diffY*diffRowBytes + diffBounds.left;
for(x=screenBounds.left; x < screenBounds.right-1; x++)
{
*diffBits = ABS(RPART16(*screenBits)-RPART16(*(screenBits+1)))
+ ABS(GPART16(*screenBits)-GPART16(*(screenBits+1)))
+ ABS(BPART16(*screenBits)-BPART16(*(screenBits+1)));
diffSum += *diffBits;
if (*diffBits > diffMax)
diffMax = *diffBits;
else if (*diffBits < diffMin)
diffMin = *diffBits;
screenBits++;
diffBits++;
}
}
/* I want the maxDiff and the minDiff to be the highest and lowest values respectively.
I was just subtracting the mid possible
difference value in the loop above, but in order for this to work well on light
text on a light background or dark text on a dark background I've decided to be
a little more picky with the difference averaging.
This won't help us with light text near dark text, but it won't hurt the high
contrast text either.
Or maybe I just want to threshold on the average contrast. That won't hurt
black on white either, since they will be max or zero contrast...
Or maybe I should threshold everything greater than zero to max.
*/
//diffMid = diffSum/((screenBounds.bottom-screenBounds.top)*(screenBounds.right-screenBounds.left));
for(y = screenBounds.top,diffY = diffBounds.top; y < screenBounds.bottom; y++,diffY++)
{
screenBits = (short*)(screenPixMapH[0]->baseAddr + y*screenRowBytes) + screenBounds.left;
diffBits = diffPixMapH[0]->baseAddr + diffY*diffRowBytes + diffBounds.left;
for(x=screenBounds.left; x < screenBounds.right-1; x++)
{
// a: threshold everything over a small min value to -max over to max
if (*diffBits >= 5)
*diffBits = MID_DIFF_VALUE_16;
else
*diffBits = -1*MID_DIFF_VALUE_16;
// if(*diffBits >= 0) (*diffBits)++;
screenBits++;
diffBits++;
}
}
UnlockPixels(screenPixMapH);
UnlockPixels(diffPixMapH);
}
/* Pick the most likely font and point size.
Find a letter in the immediate vicinity of the mouse.
(the middle of the gworld data we are given. (what about edges?))
For each font and each point size
on a rectangle pointsize*2+1 tall and maxLetterWidth*2+1 wide
correlate all the letters,
store max correlation for each letter. (Why not just max over font and point size?)
Store max correlation for font and point size allong with the letter with
max correlation and it's location.
(What about location? Closeness to the pointer should also be important.)
*/
void PickFontNPointDiff16(WordData *bestWord)
{
short midX,midY,kernelWidth,kernelHeight;
Rect searchRect,portRect;
short font,pointSize,letter;
FontData *theFontData;
GWorldPtr fontGWorld;
PixMapHandle fontPixMap,screenPixMap;
short screenRowBytes,fontRowBytes;
Ptr screenPixData, fontPixData, kernelPixData;
float fontMaxLetterScore;
short fontMaxLetter, fontMaxLetterX, fontMaxLetterY;
LetterData theLetter;
screenPixMap = GetGWorldPixMap(gScreenHDiff);
LockPixels(screenPixMap);
screenRowBytes = ROWBYTES(screenPixMap[0]->rowBytes);
screenPixData = screenPixMap[0]->baseAddr;
RECT_EQUAL(portRect,gScreenHDiff->portRect);
midY = (portRect.bottom - portRect.top)/2;
midX = (portRect.right - portRect.left)/2;
for (font=0; font<NUM_FONTS; font++)
{
for (pointSize=0; pointSize<NUM_POINT_SIZES; pointSize++)
{
theFontData = &FONT_DATA(font,pointSize);
fontGWorld = theFontData->kernelBitmap;
fontPixMap = GetGWorldPixMap(fontGWorld);
LockPixels(fontPixMap);
fontRowBytes = ROWBYTES(fontPixMap[0]->rowBytes);
fontPixData = fontPixMap[0]->baseAddr;
// Find search rect.
kernelHeight = theFontData->maxHeight;
searchRect.top = MAX(portRect.top, midY-kernelHeight);
searchRect.bottom = MIN(portRect.bottom-kernelHeight, midY+kernelHeight - kernelHeight);
fontMaxLetter = 0;
fontMaxLetterScore = 0;
for (letter=1; letter<NUM_LETTERS; letter++)
{
kernelWidth = theFontData->kernelWidth[letter];
searchRect.left = MAX(portRect.left, midX-kernelWidth);
searchRect.right = MIN(portRect.right-kernelWidth, midX+kernelWidth-kernelWidth);
kernelPixData = fontPixData + theFontData->kernelOffset[letter];
Correlate(&theLetter,&searchRect, kernelHeight, kernelWidth,
kernelPixData, screenPixData,
fontRowBytes, screenRowBytes);
if (theLetter.letterScore > fontMaxLetterScore)
{
fontMaxLetterScore = theLetter.letterScore;
fontMaxLetter = letter;
fontMaxLetterX = theLetter.x;
fontMaxLetterY = theLetter.y;
}
}
if (fontMaxLetterScore > bestWord->aveLetterScore)
{
bestWord->aveLetterScore = fontMaxLetterScore;
bestWord->letters[MID_WORD_LETTER] = fontMaxLetter;
bestWord->font = font;
bestWord->pointSize = pointSize;
bestWord->wordBounds.left = fontMaxLetterX + LETTER_LEFT_PAD;
bestWord->wordBounds.top = fontMaxLetterY;
bestWord->wordBounds.right = NEXT_LETTER_OFFSET(fontMaxLetterX, theFontData->kernelWidth[fontMaxLetter]);
bestWord->wordBounds.bottom = fontMaxLetterY + theFontData->maxHeight;
}
UnlockPixels(fontPixMap);
}
}
UnlockPixels(screenPixMap);
}
void Correlate(LetterData *bestLetter,Rect *searchRect,
short kernelHeight, short kernelWidth,
Ptr kernelPixData, Ptr screenPixData,
short fontRowBytes, short screenRowBytes)
{
short x,y,i,j;
long letterScore,maxLetterScore; // keep from casting short product to float!
Ptr kernelPixel, screenPixel, screenPixelLetterStart;
short screenRowIncrement,kernelRowIncrement;
screenRowIncrement = screenRowBytes - kernelWidth;
kernelRowIncrement = fontRowBytes - kernelWidth;
maxLetterScore = 0;
for (y=searchRect->top; y<searchRect->bottom + 1; y++)
{
screenPixelLetterStart = screenPixData + y*screenRowBytes;
for (x=searchRect->left; x<searchRect->right + 1; x++)
{
kernelPixel = kernelPixData;
screenPixel = screenPixelLetterStart + x;
letterScore = 0;
for (j=0; j<kernelHeight; j++)
{
for (i=0; i<kernelWidth; i++)
{
letterScore += *screenPixel * *kernelPixel;
screenPixel++;
kernelPixel++;
}
kernelPixel += kernelRowIncrement;
screenPixel += screenRowIncrement;
}
if (letterScore > maxLetterScore)
{
maxLetterScore = letterScore;
bestLetter->x = x;
bestLetter->y = y;
}
}
}
bestLetter->letterScore = (float)maxLetterScore/(float)(kernelHeight * kernelWidth);
}
/* pointer letter is the letter that the pointer is most nearly over. */
void GrowWord(WordData *bestWord)
{
LetterData nextLetter,lastLetter;
PixMapHandle screenPixMap, fontPixMap;
Ptr screenPixData, fontPixData;
short screenRowBytes, fontRowBytes;
Rect *screenRect;
FontData *theFontData;
short font, pointSize;
short done,wordIndex=0;
short searchLeft;
font = bestWord->font;
pointSize = bestWord->pointSize;
theFontData = &FONT_DATA(font,pointSize);
/* lock relevant gWorlds */
/* set up screen stuff*/
screenPixMap = GetGWorldPixMap(gScreenHDiff);
LockPixels(screenPixMap);
screenRowBytes = ROWBYTES(screenPixMap[0]->rowBytes);
screenPixData = screenPixMap[0]->baseAddr;
screenRect = &(gScreenHDiff->portRect);
/* set up font stuff */
fontPixMap = GetGWorldPixMap(theFontData->kernelBitmap);
LockPixels(fontPixMap);
fontRowBytes = ROWBYTES(fontPixMap[0]->rowBytes);
fontPixData = fontPixMap[0]->baseAddr;
/* first extend word to the right, then the left
If we extend tothe left first then the bounding box of the word will change
so when we set last Letter to it to start the right half, that's fucked up. */
for (searchLeft = 0; searchLeft <2; searchLeft++)
{
LETTER_EQUAL_WORD(lastLetter, *bestWord);
LETTER_EQUAL(nextLetter,lastLetter);
done = 0;
do
{
FindNextLetter(&nextLetter, searchLeft, screenPixData, screenRowBytes, screenRect, fontPixData, fontRowBytes);
if (nextLetter.letterScore < CONFIDANT_SCORE) nextLetter.letter = 0;
if ((nextLetter.x != lastLetter.x)
&& (nextLetter.letter > 0) && (nextLetter.letter <= MAX_ALPHA_LETTER))
{
if (searchLeft)
{
(bestWord->leftLetters)++;
bestWord->letters[MID_WORD_LETTER- (bestWord->leftLetters)] = nextLetter.letter;
bestWord->wordBounds.left = nextLetter.x;
}
else
{
(bestWord->rightLetters)++;
bestWord->letters[MID_WORD_LETTER+ (bestWord->rightLetters)] = nextLetter.letter;
bestWord->wordBounds.right = NEXT_LETTER_OFFSET(nextLetter.x,theFontData->kernelWidth[nextLetter.letter]);
}
UPDATE_SCORE(*bestWord,nextLetter.letterScore);
}
else
done = 1;
LETTER_EQUAL(lastLetter,nextLetter);
}while(!done);
}
UnlockPixels(fontPixMap);
UnlockPixels(screenPixMap);
}
/* assumes the relevant gWorlds are locked,
(screen horizontal difference & selected font-pointsize) */
void FindNextLetter(LetterData *refLetter, short searchLeft,
Ptr screenPixData, short screenRowBytes, Rect *screenRect,
Ptr fontPixData, short fontRowBytes)
{
Rect searchRect; // top left coords to search over.
FontData *theFont;
short letter, kernelHeight, kernelWidth, refKernelWidth;
LetterData theLetter;
Ptr kernelPixData;
short left,right;
theFont = &FONT_DATA(refLetter->font, refLetter->pointSize);
kernelHeight = theFont->maxHeight;
refKernelWidth = theFont->kernelWidth[refLetter->letter];
/* set up horizontal search, allow jitter of 20% of the pointSize? min of +-2? */
left = refLetter->x - kernelHeight/JITTER_DIVIDER;
right = refLetter->x + kernelHeight/JITTER_DIVIDER;
/* searchRect.right is right - letterWidth, so searchRect.right + letterWidth is
> screenRect.left since refX + plusMinus is. */
/* currently assume zero vertical jitter. */
searchRect.top = refLetter->y;
searchRect.bottom = refLetter->y;
refLetter->letterScore = 0;
/* correlate each letter over that interval. */
for (letter = 0; letter < NUM_LETTERS; letter++)
{
kernelWidth = theFont->kernelWidth[letter];
if(searchLeft) // searching to the left
{
searchRect.right = LAST_LETTER_OFFSET(right, kernelWidth);
searchRect.left = LAST_LETTER_OFFSET(left, kernelWidth);
if (searchRect.left < screenRect->left)
searchRect.left = screenRect->left;
}
else // searching to the right
{ /* when optimizing this should be taken out of the loop. I want to keep it
symetric for debugging. */
searchRect.right = NEXT_LETTER_OFFSET(right, refKernelWidth);
searchRect.left = NEXT_LETTER_OFFSET(left, refKernelWidth);
if (searchRect.right > screenRect->right)
searchRect.right = screenRect->right;
}
kernelPixData = fontPixData + theFont->kernelOffset[letter];
Correlate(&theLetter,&searchRect,
kernelHeight, kernelWidth,
kernelPixData, screenPixData,
fontRowBytes, screenRowBytes);
if (theLetter.letterScore > refLetter->letterScore)
{
refLetter->letterScore = theLetter.letterScore;
refLetter->letter = letter;
refLetter->x = theLetter.x;
refLetter->y = theLetter.y;
}
}
}
void MyFindWord (WordData *bestWord, GWorldPtr inGWorld)
{
HorizontalDifference(inGWorld);
ZERO_WORD(*bestWord);
PickFontNPointDiff16(bestWord);
if (bestWord->aveLetterScore < CONFIDANT_SCORE) return;
GrowWord(bestWord);
}
void CopyWordToPascalString(Str255 inString, WordData *inWord)
{
short stringIndex = 0,i;
inString[stringIndex++] = WORD_LENGTH(*inWord);
for (i = WORD_LEFT_INDEX(*inWord); i <= WORD_RIGHT_INDEX(*inWord); i++)
inString[stringIndex++] = gLetters[inWord->letters[i]];
}